package algorithm.arithmetic.汽车过桥;

import java.util.HashMap;
import java.util.Map;

/**
 * 如：输入15 44，输出21
 * @author GYFeng by 2016/11/30
 * @version 1.0
 */
public class Solution {

    private static int m[][];

    private static Map<String, Integer> cache = new HashMap<String, Integer>();

    // 单向双车道中间有座独木桥，一次只允许一辆汽车通过，每辆汽车通过所需时间不等。
    // 此时，双车道上均有车辆排队过桥，设计一种算法，使得所有车辆等待时间总和最小，并输出该总和时间。
    public static void main(String[] args) {

        // 设 M 为车道车队。M[1,x]={m[1,1],m[1,2],...,m[1,x]}表示车道为1和车辆信息。m[1,n]代码第1车道第n辆车过桥时间.x>=1
        // 同理得第二车道车辆信息
        // m[x,0]为无穷大
        // 设 MIN[x,y]为两车道分别为x，y辆车时最小等待时间。则有
        // MIN[x,y]=min(m[1,x]*(x+y-1)+MIN[x-1,y],m[2,y]*(x*y-1)+MIN[x,y-1]),min为取最小值函数 x>=1,y>=1

        // MIN[1,1]=min(m[1,1]*(1+1-1)+MIN[0,1],m[2,1]*(1+1-1)+MIN[1,0])
        // MIN[0,y]=m[2,y]*y-1+m[2,y-1]*y-2+...+m[2,2]*1+m[2,1]*0;

        m = new int[3][];
        m[1] = new int[args[0].length() + 1];
        m[2] = new int[args[1].length() + 1];

        m[1][0] = Integer.MAX_VALUE;
        m[2][0] = Integer.MAX_VALUE;

        for (int i = 1; i < args[0].length() + 1; i++) {
            m[1][i] = Integer.parseInt(args[0].substring(i - 1, i));
        }
        for (int i = 1; i < args[1].length() + 1; i++) {
            m[2][i] = Integer.parseInt(args[1].substring(i - 1, i));
        }
        System.out.println(MIN(args[0].length(), args[1].length()));
    }

    private static int MIN(int x, int y) {
        String key = x + "-" + y;
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        int min;
        if (x == 0) {
            min = oneMIN(2, y);
        } else if (y == 0) {
            min = oneMIN(1, x);
        } else {
            int m1 = m[1][x] * (x + y - 1);
            int m2 = m[2][y] * (x + y - 1);
            min = Math.min(m1 + MIN(x - 1, y), m2 + MIN(x, y - 1));
        }

        cache.put(key, min);
        return min;
    }

    private static int oneMIN(int index, int max) {
        int sum = 0;
        for (int i = 1; i <= max; i++) {
            sum += m[index][i] * (i - 1);
        }
        return sum;
    }
}
